package lc;
import java.util.*;
import org.junit.*;

public class Ex567 {
    class Solution {
        public boolean checkInclusion(String s1, String s2) {
            int[] map = new int[26];
            Set<Character> set = new HashSet<>();
            for (char c: s1.toCharArray()) {
                map[c - 'a']++;
                set.add(c);
            }
            char[] cs = s2.toCharArray();
            int len = cs.length, lo = 0, hi = 0, cnt = s1.length();
    
            loop: while (hi < len) {
                int[] cur = new int[26];
                System.arraycopy(map, 0, cur, 0, 26);
                cnt = s1.length();
                while (hi < len && cnt > 0) {
                    if (!set.contains(cs[hi])) {
                        lo = hi = hi + 1;
                        continue loop;
                    } else if (cur[cs[hi] - 'a'] == 0) {
                        while (lo < hi && cs[lo] != cs[hi]) {
                            cur[cs[lo] - 'a']++;
                            lo++;
                            cnt++;
                        }
                        cur[cs[lo] - 'a']++;
                        lo++;
                        cnt++;
                        // while (lo < hi && cs[lo] != cs[hi]) {
                        //     lo++;
                        // }
                    } else {
                        cur[cs[hi] - 'a']--;
                        cnt--;
                        if (cnt == 0) {
                            return true;
                        }
                    }
                    hi++;
                }
            }
            return false;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.checkInclusion("adc", "dcda"));        
    }
}
